#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;

/*HJJ QQ479287006
 * 力扣上面没有01 背包
 * 有N件物品和⼀个最多能被重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每
件物品只能⽤⼀次，求解将哪些物品装⼊背包⾥物品价值总和最⼤

 这是标准的背包问题，以⾄于很多同学看了这个⾃然就会想到背包，甚⾄都不知道暴⼒的解法应该怎么
解了。
这样其实是没有从底向上去思考，⽽是习惯性想到了背包，那么暴⼒的解法应该是怎么样的呢？
每⼀件物品其实只有两个状态，取或者不取，所以可以使⽤回溯法搜索出所有的情况，那么时间复杂度
就是O(2^n)，这⾥的n表示物品数量

所以暴⼒的解法是指数级别的时间复杂度。进⽽才需要动态规划的解法来进⾏优化！

 确定递推公式
i 代表 对应物品 j代表背包总重量 dp[i][j] 存入价值

一共有两种放得下和放不下
 如果放不下 dp[i][j]=dp[i-1][j] ;//等于前一个重物的
 如果放得下 dp[i][j]=dp[i-1][j] ;//为前一个的价值+现在的价值
 //其中dp(i-1,j)表示不装，dp(i-1,j-w(i))+v(i) 表示装了第i个商品，背包容量减少w(i)，但价值增加了v(i)；
 //为什么要-w(i)呢 这个才是前几个的 而并不是前一个的 -w(i) 保证可以放下 而且相当于删除前面的物品了
自己原来可能想着 奥如果j>当前物品 但是现在背包容量不能放当前物品怎么办 这个就是-w(i)的作用
 //还有一个问题 j>当前物品 而且现在背包容量够用,此时dp(i-1,j-w(i))+v(i) 这个方程也会+那个够用的背包里面的东西

 TODO 因为这个dp 只会跟上一个状态有关 可以优化成一个一维数组
 * 01 背包一样只有一个 多重背包一样有多个
 * */
void test_2_wei_bag_problem1() {
    int w[5] = {0, 2, 3, 4, 5};            //商品的体积2、3、4、5
    int v[5] = {0, 3, 4, 5, 6};            //商品的价值3、4、5、6
    int bagV = 8;                            //背包大小
    int dp[5][9] = {{0}};                    //动态规划表

    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= bagV; j++) {
            if (j < w[i])
                dp[i][j] = dp[i - 1][j];
            else
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
        }
    }

    //动态规划表的输出
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 9; j++) {
            cout << dp[i][j] << ' ';
        }
        cout << endl;
    }

    cout << dp[4][8];//10
}


///转换为1维数组 TODO
void test_1_wei_bag_problem() {

    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    int bagWeight = 4;
    // 初始化
    vector<int> dp(bagWeight + 1, 0);

    //这个遍历必须先物品 然后里面套背包 否则只是这个物品的了 （但是上面二维数组不用）
    for (int i = 0; i < weight.size(); i++) { // 遍历物品

//        i i i i
//        i i i i
//        i i i i
        //第二个初始化必须从大到小初始化 否则前面的值影响后面 多次+了
        //注意这个是j >= weight[i] 背包体积大于这里的体积才能装的下
        for (int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
            //好好理解一下吧 同一重物放在不同容量背包 需要的是前一个重物的的状态而不是当前的前一个 从后向前遍历否则会重复
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
            //此时 dp[j] 代表的就是前一个 就是下次便利的时候取dp[j]就行因为一直在更新 此时等于那时候  dp[j]=dp[i-1][j]
        }

    }
    cout << dp[bagWeight] << endl;
}